package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 783. 二叉搜索树节点最小距离
 * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
 *
 * 注意：本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [4,2,6,1,3]
 * 输出：1
 * 示例 2：
 *
 *
 * 输入：root = [1,0,48,null,null,12,49]
 * 输出：1
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [2, 100] 内
 * 0 <= Node.val <= 105
 *
 * @author SHM
 */
public class MinDiffInBST {
    public int minDiffInBST(TreeNode root) {
        int min = Integer.MAX_VALUE;
        List<Integer> list = new ArrayList<>();
        midOrder(root,list);
        int n = list.size();
        for(int i=1;i<n;i++){
            int k = list.get(i)-list.get(i-1);
            if(k<min){
                min = k;
            }
        }
        return min;
    }

    //中序遍历
    void midOrder(TreeNode root,List<Integer> list){
        if(root==null){
            return;
        }
        midOrder(root.left,list);
        list.add(root.val);
        midOrder(root.right,list);
    }


    int min;
    int pre;
    public int minDiffInBST_3(TreeNode root) {
        min = Integer.MAX_VALUE;
        pre = -1;
        middleOrder(root);
        return min;
    }


    /**
     *     //中序遍历
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)O(n)。
     *
     * 空间复杂度：O(n)O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n)O(n) 级别。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/solution/er-cha-sou-suo-shu-jie-dian-zui-xiao-ju-8u87w/
     * @param root
     */
    void middleOrder(TreeNode root){
        if(root==null){
            return;
        }
        middleOrder(root.left);
        if(pre==-1){
            pre = root.val;
        }else {
            min = Math.min(min,root.val-pre);
            pre = root.val;
        }
        middleOrder(root.right);
    }
}
